import java.util.*;

/**
 * @author ZJX
 * @version 1.0
 * @descption 回溯算法
 * @since 2025/11/10 20:22
 */
public class Backtrack {
    List<List<Integer>> ret;
    Deque<Integer> path;
    boolean[] used; // 标记数组：记录元素是否已使用

    public List<List<Integer>> subsets(int[] nums) {
        ret = new LinkedList<>();
        path = new LinkedList<>();
        dfsSubsets(nums, 0);
        return ret;
    }

    public void dfsSubsets(int[] nums, int pos) {
        ret.add(new LinkedList<>(path));
        for (int i = pos; i < nums.length; i++) {
            path.add(nums[i]);
            dfsSubsets(nums, i + 1);
            path.removeLast();
        }
    }

    public List<List<Integer>> combine(int n, int k) {
        ret = new LinkedList<>();
        path = new LinkedList<>();
        dfsCombine(n, k, 1);
        return ret;
    }

    private void dfsCombine(int n, int k, int pos) {
        if (path.size() == k) {
            ret.add(new LinkedList<>(path));
            return;
        }
        for (int i = pos; i <= n - (k - path.size()) + 1; i++) {
            path.add(i);
            dfsCombine(n, k, i + 1);
            path.removeLast();
        }
    }

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        ret = new LinkedList<>();
        path = new ArrayDeque<>();
        Arrays.sort(candidates);
        dfsCombinationSum(candidates, target, 0, 0);
        return ret;
    }

    private void dfsCombinationSum(int[] candidates, int target, int sum, int pos) {
        if (sum == target) {
            ret.add(new LinkedList<>(path));
            return;
        }
        for (int i = pos; i < candidates.length; i++) {
            int n = candidates[i];
            if (sum + n > target) {
                break; // 剪枝
            }
            path.add(n);
            sum += n;
            dfsCombinationSum(candidates, target, sum, i);
            path.removeLast();
            sum -= n;
        }
    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        ret = new LinkedList<>();
        path = new LinkedList<>();
        Arrays.sort(candidates);
        dfsCombinationSum2(candidates, target, 0, 0);
        return ret;
    }

    private void dfsCombinationSum2(int[] candidates, int target, int pos, int sum) {
        if (sum == target) {
            ret.add(new LinkedList<>(path));
            return;
        }
        for (int i = pos; i < candidates.length; i++) {
            int n = candidates[i];
            if (sum + n > target) {
                break;
            }
            if (i > pos && candidates[i] == candidates[i - 1]) {
                continue;
            }
            path.add(n);
            sum += n;
            dfsCombinationSum2(candidates, target, i + 1, sum);
            path.removeLast();
            sum -= n;
        }
    }

    public List<List<Integer>> permute(int[] nums) {
        ret = new LinkedList<>();
        path = new LinkedList<>();
        used = new boolean[nums.length];
        dfsPermute(nums);
        return ret;
    }

    private void dfsPermute(int[] nums) {
        int n = nums.length;
        if (path.size() == nums.length) {
            ret.add(new LinkedList<>(path));
            return;
        }
        for (int i = 0; i < n; i++) {
            if (used[i]) {
                continue;
            }
            path.add(nums[i]);
            used[i] = true;
            dfsPermute(nums);
            path.removeLast();
            used[i] = false;
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        ret = new LinkedList<>();
        path = new LinkedList<>();
        used = new boolean[nums.length];
        Arrays.sort(nums);
        dfsPermuteUnique(nums);
        return ret;
    }

    private void dfsPermuteUnique(int[] nums) {
        if (path.size() == nums.length) {
            ret.add(new LinkedList<>(path));
            return;
        }
        for (int i = 0; i < nums.length; i++) {
            if (used[i]) {
                continue;
            }
            if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {
                continue;
            }
            used[i] = true;
            path.add(nums[i]);
            dfsPermuteUnique(nums);
            path.removeLast();
            used[i] = false;
        }
    }

    public List<String> generateParenthesis(int n) {
        List<String> ret = new LinkedList<>();
        StringBuilder sb = new StringBuilder();
        dfsGenerateParenthesis(ret, sb, 0, 0, n);
        return ret;
    }

    private void dfsGenerateParenthesis(List<String> ret, StringBuilder sb, int open, int close, int n) {
        if (sb.length() == 2 * n) {
            ret.add(sb.toString());
            return;
        }
        if (open < n) {
            sb.append('(');
            dfsGenerateParenthesis(ret, sb, open + 1, close, n);
            sb.deleteCharAt(sb.length() - 1);
        }
        if (close < open) {
            sb.append(')');
            dfsGenerateParenthesis(ret, sb, open, close + 1, n);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public List<String> restoreIpAddresses(String s) {
        List<String> ret = new LinkedList<>();
        if (s.length() < 4 || s.length() > 12) {
            return ret;
        }
        dfsRestoreIpAddresses(ret, new StringBuilder(), s, 0, 0);
        return ret;
    }

    private void dfsRestoreIpAddresses(List<String> ret, StringBuilder curIp, String s, int start, int segments) {
        if (segments == 4) {
            if (start == s.length()) {
                ret.add(curIp.toString());
            }
            return; // 剪枝操作, 说明字符串不合理
        }
        for (int i = start; i < s.length(); i++) {
            if (i - start + 1 > 3) {
                break; // IP段最长3位
            }
            int remain = s.length() - (i + 1);
            if (remain < (3 - segments)) {
                break; // 剩余的字符不够分配
            }
            String segment = s.substring(start, i + 1);
            if (!isValidSegment(segment)) {
                continue;
            }
            int curLen = curIp.length();
            curIp.append(segment);
            if (segments < 3) {
                curIp.append('.');
            }
            dfsRestoreIpAddresses(ret, curIp, s, i + 1, segments + 1);
            curIp.setLength(curLen); // 回溯
        }

    }

    // 辅助方法：判断单个IP段是否合法
    private boolean isValidSegment(String segment) {
        return !segment.isEmpty() && segment.length() <= 3 && !(segment.length() > 1 && segment.charAt(0) == '0') && Integer.parseInt(segment) <= 255;
    }
}

